package algorithm.middle;

import java.util.*;

/**
 * 你有一个单词列表 words 和一个模式  pattern，你想知道 words 中的哪些单词与模式匹配。
 * <p>
 * 如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。
 * <p>
 * （回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
 * <p>
 * 返回 words 中与给定模式匹配的单词列表。
 * <p>
 * 你可以按任何顺序返回答案。
 */
public class FindAndReplacePattern890 {

    public List<String> findAndReplacePattern(String[] words, String pattern) {
        ArrayList<String> list = new ArrayList<>();
        int length = pattern.length();
        out:
        for (String str : words) {
            if (str.length() == length) {
                //比对规则
                //word->pattern
                HashMap<Character, Character> map = new HashMap<>();
                //pattern
                HashSet<Character> set = new HashSet<>();
                for (int i = 0; i < str.length(); i++) {
                    if (map.containsKey(str.charAt(i))) {
                        if (!map.get(str.charAt(i)).equals(pattern.charAt(i))) {
                            continue out;
                        }
                    } else {
                        if (set.contains(pattern.charAt(i))){
                            continue out;
                        }
                        map.put(str.charAt(i), pattern.charAt(i));
                        set.add(pattern.charAt(i));
                    }
                }
                list.add(str);
            }
        }
        return list;
    }
}
